package foursum

import (
	// "container/list"
	"sort"
)


func fourSum(nums []int, target int) [][]int {
	if len(nums)<4 {
		return nil
	}
	// 要求不重复 所以去重 
	sort.Ints(nums)
	// a b c d互不相同
	// 仍使用双指针法
	var res [][]int
	var n int = len(nums)
	for i:=0;i<n-3;i++{
		//判断a 是否遍历过
		if i>0 && nums[i] == nums[i-1] {
			continue
		}
		// 第二层循环固定b
		for j:=i+1; j<n-2;j++ {
			// 判断b是否遍历过
			if j>i+1 && nums[j] == nums[j-1] {
				continue
			}
			target := 0-(nums[i]+nums[j])
			// 双指针寻找c+d
			last := n-1
			for k:=j+1;k<n;k++{
				if k>j+1 && nums[k]==nums[k-1] {
					continue
				}
				for k<last && nums[k]+nums[last] > target {
					last--
				}
				if k==last{
					break
				}
				if nums[k]+nums[last] == target {
					res = append(res, []int{nums[i],nums[j],nums[k],nums[last]})
				}
			}
		}

	}
	return res
}

func fourSum1(nums []int, target int) [][]int {
	if len(nums) < 4 {
		return nil
	}
	sort.Ints(nums)
	var res [][]int
	for i := 0; i < len(nums)-3; i++ {
		n1 := nums[i]
		// if n1 > target { // 不能这样写,因为可能是负数
		// 	break
		// }
		if i > 0 && n1 == nums[i-1] {
			continue
		}
		for j := i + 1; j < len(nums)-2; j++ {
			n2 := nums[j]
			if j > i+1 && n2 == nums[j-1] {
				continue
			}
			l := j + 1
			r := len(nums) - 1
			for l < r {
				n3 := nums[l]
				n4 := nums[r]
				sum := n1 + n2 + n3 + n4
				if sum < target {
					l++
				} else if sum > target {
					r--
				} else {
					res = append(res, []int{n1, n2, n3, n4})
					for l < r && n3 == nums[l+1] { // 去重
						l++
					}
					for l < r && n4 == nums[r-1] { // 去重
						r--
					}
					// 找到答案时,双指针同时靠近
					r--
					l++
				}
			}
		}
	}
	return res
}